package com.liyghting.datastructurealgorithm.queue;

/**
 * 基于数组实现队列
 * 
 * @author LiYiGuang
 * @date 2018/11/22 14:58
 */
public class ArrayQueue {
	private String[] items;
	private int head;// 队头的数组下标
	private int tail;// 队尾的数组下标

	public ArrayQueue(int n) {
		items = new String[n];
		head = 0;
		tail = 0;
	}

	// 入队
	public boolean enqueue(String item) {
		if (tail == items.length) {
			// 数组满了，无法入队
			if (head == 0)
				return false;
			// 数组元素迁移
			for (int i = head; i < tail; i++) {
				items[i - head] = items[i];
			}
			tail = tail - head;
			head = 0;
		}
		items[tail] = item;
		tail++;
		return true;
	}

	// 出队
	public String dequeue() {
		// 队空
		if (head == tail)
			return null;
		String item = items[head];
		items[head] = null;
		head++;
		return item;
	}

	public void printAll() {
		if (head == tail)
			return;
		for (int i = head; i < tail; i++) {
			System.out.print(items[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		ArrayQueue queue = new ArrayQueue(10);
		for (int i = 0; i < 10; i++) {
			queue.enqueue(i + "");
		}
		queue.printAll();
		System.out.println(queue.head + "--" + queue.tail);

		for (int i = 0; i < 5; i++) {
			queue.dequeue();
		}
		queue.printAll();
		System.out.println(queue.head + "--" + queue.tail);

		for (int i = 0; i < 3; i++) {
			queue.enqueue(i + "");
		}
		queue.printAll();
		System.out.println(queue.head + "--" + queue.tail);

	}
}
